#include <iostream>
#include <stdio.h>
#define maxvertexnum 100
#define queuesize 100
#define null 0

typedef struct
{
	int front,rear,count,data[queuesize];
}cirqueue;//循环队列结构定义

typedef int vertextype;//为了简单，设图中结点的数据为整型
typedef struct node
{
	int adjvex;//存放邻接点序号
	struct node *next;//指向下一个边结点
}edgenode;//图的邻接表的边结点定义

typedef struct vnode
{
	vertextype vertex;//顶点数据域
	edgenode *firstedge;//指向第一个边结点
}vertexnode;//图的邻接表表示的顶点结点定义

typedef vertexnode adjlist[maxvertexnum];//用向量定义图的邻接表表示的顶点表

typedef struct
{
	adjlist adjlist;
	int n;//图的顶点数
	int e;//图的边数
}algraph;//定义图的邻接表

typedef enum{FALSE,TRUE}boolean;
boolean visited[maxvertexnum];//保存访问信息的布尔向量

main()//主函数
{//建立图g，并进行深度优先搜索和广度优先搜索
	algraph *g;
	g=(algraph*)malloc(sizeof(algraph));//申请图g的邻接表空间
	createalgraph(g);//建立图g的邻接表表示
	printf("the dfs is:");/
	dfstraverse(g);//对图g进行深度优先搜索，并打印搜索序列
	printf("the bfs is:");
	bfstraverse(g);//对图g进行广度优先搜索，并打印搜索序列
}

createalgraph(algraph *g)
{//建立图g的邻接表表示
	int i,j,k;
	int flag;
	edgenode *s;
	printf("\ncreat:\n")//选择建立有向图或无向图
		printf("digraph--0\n");
	printf("undigraph--1\n");
	scanf("%d",&flag);
	printf("input n,e\n");
	scanf("%d%d",&g->n,&g->e);//输入图g的顶点数和边数
	printf("input nodes:\n");
	for(i=0;i<g->n;i++){//构造一个只含n个顶点，边数为0的图
		scanf("%d",&(g->adjlist[i].vertex));
		//输入顶点的数据域（为了简单起见，输入为整数）
		g->adjlist[i].firstedge=null;//将顶点结点的firstedge域置为空
	}//end for
	for(k=0;k<g->e;k++){
		printf("input i,j(0~n-1):\n");
		scanf("%d%d",&i,&j);//输入对应于一条边的顶点序号序偶对，要求顶点序号为0~n-1
		s=(edgenode *)malloc(sizeof(edgenode));//申请一个边结点*s
		s->adjvex=j;//将序号j放入边结点*s的adjvex域
		s->next=g->adjlist[i].firstedge;
		//将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中
		g->adjlist[i].firstedge=s;
		if (flag){//若要建立无向图
			s=(edgenode *)malloc(sizeof(edgenode));//申请一个边结点*s
				s->adjvex=i;//将序号i放入边结点*s的adjvex域
			s->next=g->adjlist[j].firstedge;
			//将边结点*s作为第一个邻接点插入到序号为j的顶点的边表中
			g->adjlist[j].firstedge=s;
		}//end of if
	}//end of for
}//end of creatalgraph

dfs(algraph *g,int i)
{//对图g进行以序号为i的顶点作为出发点深度优先搜索
	edgenode *p;
	printf("visit vertex:%d",g->adjlist[i].vertex);//打印序号为i的顶点信息
	visited[i]=TRUE;//将序号为i的顶点设置已访问过标记
	p=g->adjlist[i].firstedge;//设置寻找序号为i的第一个未访问过邻接点的扫描指针
	while(p){
		if (!visited[p->adjvex])//若*p边结点对应顶点（假设序号为j）未访问过
			dfs(g,p->adjvex);//对图g进行以序号为j的顶点作为出发点进行深度优先搜索
		p=p->next;//p顺着边表next指针，往后继续寻找
	}//end of while
}//end of dfs

dfstraverse(algraph *g)
{//对以邻接表表示的图g进行深度优先搜索
	int i;
	for(i=0;i<g->n;i++)//将图g的所有顶点设置未访问过标记
		visited[i]=FALSE;
	for(i=0;i<g->n;i++)//对图g调用dfs函数进行深度优先搜索
		if(!visited[i])
			dfs(g,i);
	printf("\n");
}//end of dfstraverse

bfs(algraph *g, int k)
{//对图g进行以序号为k的顶点作为出发点广度优先搜索
	int i,j;
	cirqueue *q;//设置循环队列指针
	edgenode *p;
	q=(cirqueue *)malloc(sizeof(cirqueue));//申请循环队列空间
	q->rear=q->front=q->count=0;//将循环队列置为空队
	printf("visit vertex:%d",g->adjlist[k].vertex);
	visited[k]=TRUE;//将序号为k的顶点设置为已访问过
	q->data[q->rear]=k;
	q->rear=(q->rear+1)%queuesize;
	q->count++;//将顶点序号k入队
	while(q->count){//当队列非空时做以下操作
		i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--;//将队首元素i出队
		p=g->adjlist[i].firstedge;//设置寻找序号为i顶点的未访问过邻接点的扫描指针p
		while (p){//当*p不为空时，做以下操作
			if(!visited[p->adjvex]){//若*p边结点对应顶点（假设序号为j）未访问过
				printf("visit vertex:%d",g->adjlist[p->adjvex].vertex);
				//访问序号为j的顶点
				visited[p->adjvex]=TRUE;//设置已访问过标记
				q->data[q->rear]=p->adjvex;q->rear=(q->rear+1)%queuesize;q->count++;
				//将序号为j的顶点入队
			}//end of if
			p=p->next;//p顺着边表next指针，往后继续寻找
		}//end of while
	}//end of while
}//end of bfs

bfstraverse(algraph *g)
{//对以邻接表表示的图g进行广度优先搜索
	int i;
	for(i=0;i<g->n;i++)//将图g的所有顶点设置未访问过标记
		visited[i]=FALSE;
	for(i=0;i<g->n;i++)//对图g调用bfs函数进行广度优先搜索
		if(!visited[i])
			bfs(g,i);
	printf("\n");
}

